0898. 子数组按位或操作【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 集合

1. 📝 题目描述

• leetcode

给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。

子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。

子数组 是数组内连续的非空元素序列。

---

示例 1：

输入：arr = [0]
输出：1
解释：
只有一个可能的结果 0。

示例 2：

输入：arr = [1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3。
有三个唯一值，所以答案是 3。

示例 3：

输入：arr = [1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7。

---

提示：

• 1 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 10^9

2. 🎯 s.1 - 集合

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int subarrayBitwiseORs(int* arr, int arrSize) {
    int cap = arrSize * 32;
    int* all = (int*)malloc(sizeof(int) * cap);
    int allSize = 0;
    int prev[32], cur[32];
    int prevSize = 0;
    for (int i = 0; i < arrSize; i++) {
        int curSize = 0;
        cur[curSize++] = arr[i];
        for (int j = 0; j < prevSize; j++) {
            int v = prev[j] | arr[i];
            bool found = false;
            for (int k = 0; k < curSize; k++) if (cur[k] == v) { found = true; break; }
            if (!found) cur[curSize++] = v;
        }
        for (int j = 0; j < curSize; j++) all[allSize++] = cur[j];
        memcpy(prev, cur, sizeof(int) * curSize);
        prevSize = curSize;
    }
    qsort(all, allSize, sizeof(int), cmp);
    int res = allSize > 0 ? 1 : 0;
    for (int i = 1; i < allSize; i++) if (all[i] != all[i - 1]) res++;
    free(all);
    return res;
}

js

/**
 * @param {number[]} arr
 * @return {number}
 */
var subarrayBitwiseORs = function (arr) {
  const res = new Set()
  let prev = new Set()
  for (const num of arr) {
    const cur = new Set([num])
    for (const p of prev) cur.add(p | num)
    for (const v of cur) res.add(v)
    prev = cur
  }
  return res.size
}

py

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        res = set()
        prev = set()
        for num in arr:
            cur = {num | p for p in prev} | {num}
            res |= cur
            prev = cur
        return len(res)

• 时间复杂度：$O(n\log W)$，其中 n 是数组长度，W 是最大值，每个位置最多 $\log W$ 个不同 OR 值
• 空间复杂度：$O(n\log W)$

算法思路：

• 维护以当前元素结尾的所有子数组 OR 值的集合
• 每步将前一位置的集合全部与当前元素 OR，加入总结果集